package com.ds.array;

import java.util.Arrays;

public class SortedArrayMerge {

	public int[] sortedArrayMerge(int[] arr1, int[] arr2) {

		//[1]创建一个新数组，作为结果数组，结果数组的长度是两个参数数组长度之和
		int[] resultArray = new int[arr1.length + arr2.length];

		//[2]分别创建两个变量，用来遍历两个数组
		int i = 0;  //变量i遍历arr1数组
		int j = 0;  //变量j遍历arr2数组

		//[3]同时还得创建第三个变量，用来控制结果数组下标的变化
		int k = 0;  //变量k控制结果数组下标的变化

		//[4]使用循环比较arr1[i]和arr2[j]之间的大小关系，将较小的一个元素落入结果数组中
		while(i < arr1.length && j < arr2.length) {  //循环结束条件是其中的某一个数组已经被遍历完成

			//谁小谁就落在结果数组中，哪一个参数数组的元素落在结果数组中，哪一个参数数组的下标就向前进1
			if(arr1[i] < arr2[j]) {
				resultArray[k] = arr1[i];
				i++;
			}else {
				resultArray[k] = arr2[j];
				j++;
			}

			//但是不管是哪一个参数数组中的元素落入结果数组，结果数组的下标都要+1
			k++;

		}

		//[5]为了防止其中一个数组已经遍历结束，另一个数组中还有剩余元素，将另一个数组中的剩余元素全部直接拷贝到结果数组中
		if(i < arr1.length) {  //arr1没有遍历完成
			while(i < arr1.length) {
				resultArray[k] = arr1[i];
				i++;
				k++;
			}
		}

		if(j < arr2.length) {  //arr2没有遍历完成
			while(j < arr2.length) {
				resultArray[k] = arr2[j];
				j++;
				k++;
			}
		}

		//[6]返回结果数组
		return resultArray;

	}

	public static void main(String[] args) {

		int[] arr1 = new int[] {1,3,4,5,7};
		int[] arr2 = new int[] {0,1,5,7,7,8,9};

		SortedArrayMerge sam = new SortedArrayMerge();

		int[] resultArray = sam.sortedArrayMerge(arr1, arr2);
		System.out.println(Arrays.toString(resultArray));

	}

}
